package com.congee02.graph;

public class FindCircleNum {

    public int findCircleNum(int[][] isConnected) {

        int n = isConnected.length;

        boolean[] visited = new boolean[n];

        int ans = 0;
        for (int i = 0 ; i < n ; i ++ ) {
            if (! visited[i]) {
                ans ++;
                dfs(i, visited, isConnected);
            }
        }

        return ans;
    }

    private void dfs(int cur, boolean[] visited, int[][] isConnected) {

        visited[cur] = true;

        int[] to = isConnected[cur];

        for (int i = 0 ; i < to.length ; i ++ ) {
            if (to[i] == 1 && ! visited[i]) {
                dfs(i, visited, isConnected);
            }
        }

    }

}
